from typing import List


class Node:
    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):
        self.val = val
        self.isLeaf = isLeaf
        self.topLeft = topLeft
        self.topRight = topRight
        self.bottomLeft = bottomLeft
        self.bottomRight = bottomRight
        
"""
# Definition for a QuadTree node.
class Node:
    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):
        self.val = val
        self.isLeaf = isLeaf
        self.topLeft = topLeft
        self.topRight = topRight
        self.bottomLeft = bottomLeft
        self.bottomRight = bottomRight
"""

class Solution:
    def construct(self, grid: List[List[int]]) -> 'Node':
        return self.dfs(grid, 0, 0, len(grid), len(grid))
    
    def dfs(self, grid, r0, c0, r1, c1):
        isLeaf = True
        for r in range(r0, r1):
            for c in range(c0, c1):
                if grid[r][c] != grid[r0][c0]:
                    isLeaf = False
                    break
        
        if isLeaf:
            return Node(grid[r0][c0] == 1, True)
        
        return Node(
            True, 
            False, 
            self.dfs(grid, r0, c0, (r0 + r1) // 2, (c0 + c1) // 2),
            self.dfs(grid, r0, (c0 + c1) // 2, (r0 + r1) // 2, c1),
            self.dfs(grid, (r0 + r1) // 2, c0, r1, (c0 + c1) // 2),
            self.dfs(grid, (r0 + r1) // 2, (c0 + c1) // 2, r1, c1)
        )

